#include <stack>
#include <utility>
#include <vector>
using namespace std;
// 穷举遍历 O(N^2)
vector<int> dailyTemperatures(vector<int> &temperatures) {
  vector<int> res;
  for (int i = 0; i < temperatures.size() - 1; ++i) {
    bool flag = false;
    for (int j = i + 1; j < temperatures.size(); ++j) {
      if (temperatures[i] < temperatures[j]) {
        flag = true;
        res.push_back(j - i);
        break;
      }
    }
    if (!flag) {
      res.push_back(0);
    }
  }
  res.push_back(0);
  return res;
}

vector<int> dailyTemperatures_(vector<int> &temperatures) {
  vector<int> res(temperatures.size(), 0);
  stack<int> s;
  for (int i = 0; i < temperatures.size(); ++i) {
    while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
      int t = s.top();
      s.pop();
      res[t] = i - t;
    }
    s.push(i);
  }
  return res;
}
